package m202311.d07;

/**
 * @author haocongshun
 * @date 2023/11/07 19:07:49
 */

import java.util.*;

/**
 * 380. O(1) 时间插入、删除和获取随机元素
 */
public class Q380 {

    public static void main(String[] args) {
        RandomizedSet randomizedSet = new RandomizedSet();
        randomizedSet.insert(0);
        randomizedSet.remove(0);
        randomizedSet.insert(0);
        randomizedSet.getRandom();
        for (int i = 0; i < 1000; i++) {
            System.out.println(randomizedSet.getRandom());
        }
    }

    public static class RandomizedSet {

        private final List<Integer> list;
        private final Map<Integer, Integer> map;

        private final Random random;

        public RandomizedSet() {
            list = new ArrayList<>();
            map = new HashMap<>();
            random = new Random();
        }

        public boolean insert(int val) {
            if (map.containsKey(val)) {
                return false;
            }
            list.add(val);
            map.put(val, list.size() - 1);
            return true;
        }

        public boolean remove(int val) {
            if (!map.containsKey(val)) {
                return false;
            }
            Integer index = map.get(val);
            Integer last = list.get(list.size() - 1);
            list.set(index, last);
            map.put(last, index);
            list.remove(list.size() - 1);
            map.remove(val);
            return true;
        }

        public int getRandom() {
            int i = random.nextInt(list.size());
            return list.get(i);
        }
    }
}
